package leetcode101_xqzhao

// TODO 【没思路】 LRU 缓存 【-】 双向循环链表 + 哈希表

type LRUCache struct {
	IMap    map[int]*BiListNode
	IBiList *BiList
	cap     int // 最大容量
}

func Constructor(capacity int) LRUCache {
	lru := LRUCache{
		IMap:    make(map[int]*BiListNode, 0),
		IBiList: NewBiList(), // NewBiList() 返回的是地址 (即指针)
		cap:     capacity,
	}
	return lru
}
func (this *LRUCache) Get(key int) int {
	if _, ok := this.IMap[key]; !ok {
		return -1
	} else {
		node := this.IMap[key]
		this.IBiList.Remove(node)
		this.IBiList.PutLast(node)
		return node.Val
	}
}

func (this *LRUCache) Put(key int, value int) {
	newNode := &BiListNode{
		key: key,
		Val: value,
	}
	if _, ok := this.IMap[key]; ok { // key 已经存在于 IMap 中
		this.IBiList.Remove(this.IMap[key])
		delete(this.IMap, key)
	} else if this.IBiList.size == this.cap {
		// key 不存在, 并且 BiList 存满了, 启动淘汰机制
		first := this.IBiList.RemoveFirst()
		delete(this.IMap, first.key)
	}
	this.IBiList.PutLast(newNode)
	this.IMap[key] = newNode
}

// 双向循环链表节点
type BiListNode struct {
	key, Val int
	Prev     *BiListNode
	Next     *BiListNode
}

// 双向循环链表: 属性为: 头结点、尾结点、结点数量
type BiList struct {
	Head *BiListNode
	Tail *BiListNode
	size int
}

// 初始化双向循环链表
func NewBiList() *BiList {
	biList := &BiList{}
	biList.Head = &BiListNode{}
	biList.Tail = &BiListNode{}
	biList.Head.Next, biList.Head.Prev = biList.Tail, biList.Tail
	biList.Tail.Next, biList.Tail.Prev = biList.Head, biList.Head
	biList.size = 0
	return biList
}

// 往末尾节点插入
func (this *BiList) PutLast(node *BiListNode) {
	node.Next = this.Tail
	node.Prev = this.Tail.Prev
	node.Prev.Next = node
	this.Tail.Prev = node
	this.size++
}

// 移除并返回头节点
func (this *BiList) RemoveFirst() *BiListNode {
	if this.Head.Next == this.Tail {
		return nil
	}
	node := this.Head.Next
	// 直接调用已经实现的删除节点函数
	this.Remove(node)
	return node
}

// 删除某个节点 - 通过调用函数判断该节点是否存在
func (this *BiList) Remove(node *BiListNode) {
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
	this.size--
}

// 长度
func (this *BiList) Len() int {
	return this.size
}
